package practice1_100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Practice368 {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        //用动态规划找出最长的子序列
        Arrays.sort(nums);
        ArrayList<Integer> list=new ArrayList();
        int[] maxLen=new int[nums.length];//这个用来存储，到了第i长度的时候，最长的最大整除子序列有多少个
        Arrays.fill(maxLen,1);
        int[] index=new int[nums.length];
        for (int i = 1; i < nums.length; i++) {
            int temp=0;
            for (int j = 0; j < i ; j++) {
                if(nums[i]%nums[j]==0){
                    maxLen[i]=maxLen[i]>maxLen[j]+1?maxLen[i] :maxLen[j]+1;
                    index[i]=j;
                }
            }
        }
        int i=maxLen[maxLen.length-1];
        for (int j = nums.length-1; j >=0&&i>=1 ; j--) {
            list.add(nums[j] );
            i--;

        }
        return  list;
    }

    public static void main(String[] args) {
       List<Integer> list= new Practice368().largestDivisibleSubset(new int[]{1,2,3,4,8,9,18,36});
        System.out.println(list);

    }
}
